from __future__ import print_function
import math
from GeometricalObjects import *
from GenerateUtilities import *
from SearchUtilities import * 

import os
'''
PARAMETERS OF THE PROGRAM
- nb_points: the amount of points to generate, must be between nb_steps and max_x * max_y
- nb_steps: the amount of points to go through from starting point (A) before reaching final point (B)
- max_x: maximum amount of rows of the grid
- max_y: maximum amount of columns of the grid
'''

nb_points = 800 
nb_steps = 6 
max_x = 99 # nb rows large screen : 24
max_y = 35 # nb cols large screen : 35

def add_display_point(point, letter, txt_points, minx,miny,maxx,maxy):
	#print("{0} {1}".format(len(txt_points),len(txt_points[0])))
	#print("{0} {1}".format(point.x,point.y))
	row = int(point.x-minx)
	col = int(point.y-miny)
	if txt_points[row][col] != " ":
		print("{0} overwritten by {1}".format(txt_points[row][col], letter))
	if txt_points[row][col] != "A" and txt_points[row][col]!= "B":
		txt_points[row][col] = letter

def display_x_axis(miny,maxy):
	print("{0:4}".format(""),end="")
	for col in range(maxy-miny):
		print("{0:4}".format(col+miny),end="")
	print()


def display_points( points, max_x, max_y):
	txt_points = []
	minx, miny, maxx, maxy = max_x, max_y, 0, 0
	for p in points:
		minx, maxx = min(minx,p.x), max(maxx,p.x)
		miny, maxy = min(miny,p.y), max(maxy,p.y)
	maxx += 1
	maxy += 1
	for row in range(maxx-minx):
		txt_points.append([" "] * (maxy-miny))
	for p in points:
		add_display_point(p, p.name, txt_points,minx,miny,maxx,maxy)
	display_x_axis(miny,maxy)	
	for idx,row in enumerate(txt_points):
		print("{0:4} ".format(idx+minx),end="")
		for point in row:
			print("{0:4}".format(point),end="")
		print()
	display_x_axis(miny,maxy)

def discard_too_far_away_points(A, B, points, best_length):
	points_to_remove = []
	for p in points:
		dist = distance_3_points(A,B,p)
		#print("{0} and {1}".format(dist, best_length))
		if distance_3_points(A,B,p) > best_length:
			points_to_remove.append(p)
	print("Removing {0} too far away points".format(len(points_to_remove)))
	for p in points_to_remove:
		points.remove(p)

def find_k_closest_points(A, B, points, k):
	closest_points = [ (i, distance_3_points(A,B,points[i])) for i in range(k) ] 
	for idx in range(k):
		for idx2 in range(idx+1,k):
			if closest_points[idx2][1] < closest_points[idx][1]:
				closest_points[idx] , closest_points[idx2] = closest_points[idx2], closest_points[idx]		
	for p_idx, p in enumerate(points[k:]):
		dist = distance_3_points(A,B,p)
		#print("{0}:{2},{3} is at distance A,B {1}".format(p.name, dist,p.x,p.y))
		for pos, best_pair in enumerate(closest_points):	
			#print("better {0} is at distance {1}".format(points[best_pair[0]].name,best_pair[1]))
			if dist < best_pair[1]:
				closest_points[pos+1:] = closest_points[pos:k-1]	
				closest_points[pos] = (p_idx + k , dist)
				break
	dist_closest_points = [ points[p[0]] for p in closest_points]
	return dist_closest_points

points = generate_points(nb_points, max_x, max_y)
#print("{0}".format(points))

A = generate_point("A", max_x, max_y)
B = generate_point("B", max_x, max_y)
A = Point("A", 0, 0)
B = Point("B", max_x-1, max_y-1)
A = Point("A", max_x/2, max_y/2)
B = Point("B", A.x+1, A.y+1)

#Displaying some useful info about A, B, and the problem configuration
print("Points generated: {0}".format(nb_points))
print("Intermediate step/points asked: {0}".format(nb_steps))
print("Name = {0} : x,y = {1},{2}".format(A.name, A.x, A.y))
print("Name = {0} : x,y = {1},{2}".format(B.name, B.x, B.y))
print("Dist A,B : {0}".format(distance(A,B)))

#Displaying points configuration
display_points( points + [A,B], max_x, max_y)

#Finding the nb_steps points with minimum distance (A->point->B)
dist_closest_points = find_k_closest_points(A, B, points, nb_steps)

#Solving problem with this very small subset of points... complexity is "nb_steps!"
import time
solver_basic = Searcher_Basic()
print("\n________ SOLVING PROBLEM WITH FIRST HEURISTIC: K points with minimal distance A->point->B  _______\n")
print("Set of closest points selected for first solve: {0} points".format(len(dist_closest_points)))
for o in dist_closest_points: print("{0}".format(o.name),end=' ')
print()
display_points(dist_closest_points + [A , B], max_x, max_y)
#os.sys.exit()
t0 = time.time()
closest_best_route = solver_basic.launch_dijkstra(A,B,nb_steps,dist_closest_points, max_x, max_y)
t1 = time.time()
print("First heuristic route in  {0}s:".format(t1-t0))
closest_best_route.print_route()

discard_too_far_away_points(A,B,points, closest_best_route.length())
print("\n________ SOLVING PROBLEM WITH SECOND HEURISTIC: K points with minimal distance A->point->B  + K points with minimal distance to A + K points with minimal distance to B _______\n")
dist_closest_points_2 = list(set([ ] + dist_closest_points + find_k_closest_points(A, A, points, nb_steps) + find_k_closest_points(B, B, points, nb_steps)))
print("Set of closest points selected for second solve: {0}".format(len(dist_closest_points_2)))
for o in dist_closest_points_2: print("{0}".format(o.name),end=' ')
print()
for o in find_k_closest_points(A, A, points, nb_steps): print("{0}".format(o.name),end=' ')
print()
for o in find_k_closest_points(B, B, points, nb_steps): print("{0}".format(o.name),end=' ')
print()
display_points(dist_closest_points_2 + [A , B], max_x, max_y)
t2 = time.time()
closest_best_route = solver_basic.launch_dijkstra(A,B,nb_steps,dist_closest_points_2, max_x, max_y)
t3 = time.time()
print("Second heuristic route in {0}s".format(t3-t2))
closest_best_route.print_route()
#Removing points whose distance (A->point->B) is superior to the best route found previously
discard_too_far_away_points(A,B,points, closest_best_route.length())

#Displaying selected points
print("\n________ SOLVING PROBLEM WITH POINTS WHOSE DISTANCE A->point->B is smaller than best route obtained with heuristics  _______\n")

display_points(points + [A , B], max_x, max_y)
print("Final set of points selected: {0} points".format(len(points)))
for o in points: print("{0} ".format(o.name),end='')
print()

#Computing optimal best route
deb = time.time()
last_best_route = solver_basic.launch_dijkstra(A,B,nb_steps,points, max_x, max_y)
mid = time.time()
#Displaying best route
print("Final route found with final set of closest points in {0}s: ".format(mid-deb))
last_best_route.print_route()

#Testing final best route is better than first heuristic one...		
if last_best_route.length() > closest_best_route.length():
	print("Error: last_best_route > best_route, which means the theory behind the approximation of the solution is wrong")
	os.sys.exit(2000)
